Historically, main memory was physically situated on a central bus. Within this type of system, memory requests consisting of full physical addresses, were forwarded to the memory subsystem and the data was returned. In a distributed memory system, main memory is physically distributed across many different cells. A cell may consist of a number of processors, an input/output (I/O) device, a cell controller, and memory.
In a distributed system, memory can be non-interleaved or interleaved. Prior art systems of and methods for interleaving memory are described and set forth in, for example, U.S. Pat. No. 5,530,837, entitled METHODS AND APPARATUS FOR INTERLEAVING MEMORY TRANSACTIONS INTO AN ARBITRARY NUMBER OF BANKS, issued Jun. 25, 1996 to Williams et al. and U.S. Pat. No. 5,293,607, entitled FLEXIBLE N-WAY MEMORY INTERLEAVING, issued Mar. 8, 1994 to Brockmann et al. U.S. Pat. Nos. 5,530,837 and 5,293,607 are assigned to the owner of the present invention, and both patents are incorporated herein by reference in their entireties. In a non-interleaved access method wherein memory is divided into or across multiple physical cells, a unified, contiguous block of memory space is addressed by first sequentially accessing all memory of a first cell followed by sequential access of all memory available in a second cell, etc. If each cell has been configured with its maximum amount of possible memory, the memory will appear, and be addressed as one contiguous memory block to the system. However, if not every cell is configured to its maximum memory capability, this non-interleaved scheme may result in holes within the memory space corresponding to missing memory blocks within the cells. Non-interleaved memory also requires multiple, sequential accesses to a particular cell since both instructions and data tend to be used sequentially. While a benefit when stored locally, a processor continuously or frequently accessing a remote memory in another cell consumes significant overhead including processing and communications resources at both the local and remote cells and the connecting network(s). When substantially continuous, these resources may become unavailable to other processes and degrade system performance.
Alternatively, the memory within a distributed memory system can be accessed through an interleaving protocol. Interleaving memory across several cells allows for more uniform access to memory. For example, if a system includes two cells that are connected together through a bus system, with each cell including memory and four separate processors, by interleaving the memory in cell 1 with the memory in cell 2, all eight processors in the system have a more uniform access to each memory location. Interleaving memory across the two cells also ensures consistency in latency delays for each processor in accessing memory locations. Interleaving memory across the two memory locations also reduces the possibility of bottlenecks when processors attempt to access or retrieve information from memory.
As an example of interleaving, assume that the memory contained within a system is distributed across four cells labeled 0, 1, 2, and 3. Further assume that each of cell 0 and cell 1 contain eight gigabytes (GB) of memory, while cells 2 and 3 each contain four GB of memory. The overall system therefore contains twenty-four GB of memory. The distributed memory could be interleaved as follows. Since each of the four cells contains at least four GB of memory, the first interleave entry, entry 0, would contain four GB of memory from each of cell 0, 1, 2, and 3 for a total of sixteen GB of memory. All of the memory available in cell 2 and cell 3 have now been used in interleave entry 0. Cell 0 and cell 1 each contain four GB of unused memory. Interleave entry 1 would contain the four GB of memory from cell 0 and the four GB of memory from cell 1. Interleave entry 1 therefore contains eight GB of memory, four from cell 0 and four from cell 1. The twenty-four GB of memory in the four cells have now been broken out into two interleave entries. The twenty-four GB of memory from the four cells can now be viewed as one contiguous block as follows. GB 0 through 15 are located in the lower half of cells 0, 1, 2, and 3, GB16 through 23 are located in the upper portion of cells 0 and 1. This interleaving occurs at the cache line level. To a processor, the twenty-four GB of information appears to be one contiguous block. While the twenty-four GB of information appears to be one contiguous block, physically the twenty-four GB of information is distributed among four different cells.
Large computer systems have used cell maps to distribute processor accesses around to avoid hot spots. Cell maps have been used to find destination modules for the cell/node based systems. Cell maps have been used to interleave memory across cells to provide a more uniform access pattern to the memory. Cell map entries have been used to provide one, two, four, eight, sixteen, thirty-two, and sixty-four way interleaving. The size of cell map entries determines how many ways the memory is interleaved.
In previous systems that used cell maps, the number and size of cell map entries had to be predetermined. To do higher-way interleaving, the cell map structures had to be designed up-front accordingly. The number of ways of interleaving that can be used is dependent on the size of the system, memory configuration and other parameters. More entries with more ways of interleave use more resources. In some previous systems, there had been a need for higher-way interleaving, but the system resources were limited, requiring lower-ways of interleave per entry, or reserving only a subset of the entries for higher-way interleaving, with the remainder of the entries providing lower-way interleaving. In previous systems, the cell maps were not always used very efficiently, and were not scaleable to provide more ways of interleaving.
It would be desirable to achieve higher-ways of interleaving by combining lower-way interleave entries.